package _剑指offer.二叉树;

import util.TreeNode;
import org.junit.Test;

public class _68_2_二叉树的最近公共祖先 {
    @Test
    public void main() {
        Integer[] input = new Integer[]{3,5,1,6,2,0,8,null,null,7,4};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println("lowestCommonAncestor = " + lowestCommonAncestor(root, new TreeNode(5), new TreeNode(1)).val);
    }
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p.val == root.val || q.val == root.val) {
            return root;
        }
        
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        
        if (l == null) {
            return r;
        } else if (r == null) {
            return l;
        } else {
            return root;
        }
    }
    
}
